{\magonebf 4.5 Hashing arrays (h\_array)}

An instance $A$ of the data type $h\_array$ (hashing array) is an injective
mapping from a data type $I$, called the index type of $A$, to a set of 
variables of a data type $E$, called the element type of $A$.  $I$ must
be $char$, $int$, a pointer type, or an item type.


\bigskip
{\bf 1. Declaration of an hashing array type}


\decltwo h\_array I E 

introduces a new data type with name \name\ consisting of all h\_arrays 
with index type $I$ and element type $E$.


\bigskip
{\bf 2. Creation of a h\_array }


\create A (x)

creates an injective function $a$ from $I$ to the set of unused variables of 
type $E$, assigns $x$ to all variables in the range of $a$ and initializes $A$
with $a$.



\bigskip
{\bf 3. \operations}

\+\cleartabs & \hskip 1.8truecm & \hskip 5truecm &\cr
\+\opa E\&   {I\ x}  
                      {returns the variable $A(x)$}
\smallskip
\+\op bool defined {I\ x}
                {returns true if $x \in dom(A)$, false otherwise; here}
\+\nop          {$dom(A)$ is the set of all $x\in I$ for which $A[x]$ has}
\+\nop          {already been executed.}

\bigskip
{\bf 4. Iteration}

{\bf forall\_defined}($x,A$) 
$\{$ ``the elements from $dom(A)$ are successively assigned to $x$'' $\}$


\bigskip
{\bf 5. Implementation}

Hashing arrays are implemented by dynamic perfect hashing ([DKMMRT88]). 
Access operations $A[x]$ take time $O(1)$. Hashing arrays are more efficient 
than dictionary arrays.

